//给你一个整数数组 nums，请你将该数组升序排列。
//
//你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。
import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;

public class test2 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = in.nextInt();
        }
        System.out.println(Arrays.toString(sortArray(nums)));;
    }

    public static int[] sortArray(int[] nums) {
        //调用函数
        int left = 0,right = nums.length-1;
        getSort(nums,left,right);
        return nums;
    }
    public static void getSort(int[] nums,int start,int end){
        if(end-start<=0){
            return;
        }
        //分成三段
        int key=nums[new Random().nextInt(end-start+1)+start];
        int left=start-1,right=end+1,i=start;
        while (i<right){
            //比较
            if(nums[i]<key){
                swap(nums,++left,i++);
            } else if (nums[i]==key) {
                i++;
            }else {
                swap(nums,--right,i);
            }
        }
        //已经分了段数
        getSort(nums,start,left);
        getSort(nums,right,end);
    }
    public static void swap(int[] nums,int index1,int index2){
        int tmp=nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = tmp;
    }
}
